Abstract: Steganography refers to the practice of hiding secret messages in communications over a public channel so that an eavesdropper (who listens to all communications) cannot even tell that a secret messages are being sent. We give a precise model of a communication channel and a rigorous definition of steganographic security and prove that relative to a channel oraclesecure steganography exists if and only if one way exist function. We are given tightly matching upper and lower bounds on the maximum rate of any secure stego system. We introduce the concept of steganographic key exchange and public-key steganographyand show that provably secure protocols for these objectives exist under a variety of standard number-theoretic assumptions. We extend the concept of steganography as covert communication to include the more general concept of covert computation.

Keywords: Discrete Cosine Transformation, Graphics Interchange Format, Joint Photographic Experts Group.